package com.peng.leetcode.tree;

import java.net.URLDecoder;
import java.net.URLEncoder;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Codec
 * 剑指 Offer 37. 序列化二叉树
 * <p>
 * 二叉树的序列化和反序列化
 *
 * @author: lupeng6
 * @create: 2021/4/14 21:09
 */
public class Codec {

    public static void main(String[] args) {
        TreeNode root = TreeMain.array2tree(new Integer[]{1, 2, 3, null, null, 4, 5});
        Codec codec = new Codec();
        String serialize = codec.serialize(root);
        System.out.println(serialize);


        TreeNode treeNode = codec.deserialize(serialize);
        System.out.println(treeNode);
    }


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder builder = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                builder.append(URLEncoder.encode("null"));
            } else {
                builder.append(URLEncoder.encode("" + node.val));
                queue.offer(node.left);
                queue.offer(node.right);
            }
            builder.append("=");
        }

        String answer = builder.toString();
        answer = answer.substring(0, answer.length() - 1);
        return answer;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArr = data.split("=");
        Queue<TreeNode> queue = new LinkedList<>();

        int index = 0;
        TreeNode root = new TreeNode(Integer.valueOf(URLDecoder.decode(dataArr[index++])));
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!dataArr[index].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(URLDecoder.decode(dataArr[index])));
                queue.offer(node.left);
            }
            index++;

            if (!dataArr[index].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(URLDecoder.decode(dataArr[index])));
                queue.offer(node.right);
            }
            index++;
        }

        return root;
    }

}
